The Asynchronous Transfer Mode technique is a transmission technique for transmitting data through a trunk and exchange network. The ATM technique provides a uniform backbone transmission format which is used to transmit data belonging to a variety of applications such as high resolution video, voice communications and terminal and computer connections. An important advantage of the ATM technique is that different transmission formats are not needed in the trunk and exchange network for different applications, but rather a single format is suitable for multiple applications.
In the ATM transmission technique, data from various services are transmitted in small fixed length packets known as cells. Each ATM data cell has an address embedded in a header which identifies the destination of the cell. These data cells are inserted into slots which form the payload envelopes of the frames of a signal such as the Synchronous Optical Network (SONET) STS-3c or STS-12c signals. The technique is called the Asynchronous Transfer Mode because the individual slots of a frame are not synchronously reserved for specific applications, but instead, the individual slots of a frame are occupied by the data cells of the specific applications based on the current availability of slots and the current demand for transmission capacity by the specific applications.
Currently, ATM networks operate at a minimum of 155.52 Mb/sec (SONET STS-3c) with a cell size of 53 bytes comprising a 5 byte header and a 48 byte payload. This corresponds to a bit time of 6.4 ns and a cell time of 2.83 .mu.s. From the standpoint of building a switch for use in a trunk and exchange network to switch ATM cells, the short cell time poses a problem, because the switch must reconfigure itself for every ATM cell entering the switch.
To overcome the reconfiguration problem a switch for switching ATM cells may make use of a Batcher-banyan network. The Batcher-banyan network is a self-routing network which, in a switch cycle, is capable of routing a plurality of packets or data cells which synchronously arrive at the network inputs to the network outputs without centralized control. The routing of each cell through the Batcher-banyan network is determined by an address contained in the cell header.
The Batcher-banyan network comprises a Batcher sorting network followed by a banyan routing network. The function of the Batcher sorting network is to arrange a set of incoming data cells in ascending or descending order according to their destination addresses. The function of the banyan network is to route the sorted data cells to the outputs indicated by the destination addresses.
A banyan network can route a data cell from any input to any specific output indicated by an address in the cell, but may suffer from internal congestion when two or more cells attempt to be routed to the same output at the same time. However, the banyan network is internally non-blocking if in a particular switch cycle no more than one incoming cell is addressed to each banyan output and the cells are arranged in ascending or descending order when they arrive at the banyan inputs. Therefore, it is possible to construct a non-blocking network by combining a Batcher sorting network and a banyan routing network.
An N-input by N-output (NxN) Batcher or banyan network is formed by a rectangular array of 2.times.2 switching elements. Each Batcher or banyan switching element has first and second inputs (i.sub.0 and i.sub.i) and first and second outputs (O.sub.0 and O.sub.1). The inputs and outputs are connected in a pass state (i.sub.0 .fwdarw.O.sub.0, i.sub.1 .fwdarw.O.sub.1) or a cross state (i.sub.0 .fwdarw.O.sub.0, i.sub.1 .fwdarw.O.sub.1) according to the value of particular bits in the data cells present at the two inputs. Each 2.times.2 switching element includes state determination logic which determines whether the switching element should change its state (from pass to cross or from cross to pass) for the particular data cells present at the first and second inputs. The state determination logic is different depending on whether the switching element is a Batcher element or a banyan element.
Illustratively N is 256 so that a Batcher-banyan network may accommodate up to 256 cell channels. By using VLSI technology, many of the 2.times.2 processing elements may be implemented in a single VLSI chip.
One way to increase the speed of such a large Batcher-banyan network so that it may be used to switch ATM cells is to utilize the unique chip designs disclosed in U.S. Pat. No. 4,910,730. This patent discloses a Batcher-banyan network which may be implemented using only two different IC chip designs. The chips are arranged in adjacent vertical and horizontal stacks to minimize the length of electrical conductors connecting the chips. This minimizes propagation delays between chips in the Batcher-banyan network and places the speed bottleneck on the individual 2.times.2 switching elements.
A variety of designs for the 2.times.2 switching elements utilized in a Batcher-banyan network have been proposed (see, e.g., N. H. E. Weste and K. Eshrghian, "Principles of CMOS VLSI Design", Addison Wesley, Reading, Mass., 1985, pp 439, and the above-mentioned U.S. Pat. No. 4,910,730). However, these prior art 2.times.2 switching cells are highly complex and/or are too slow to process bit streams comprising ATM cells.
Accordingly, it is an object of the present invention to provide a design for the 2.times.2 switching elements utilized in Batcher and banyan networks, which design is fast enough to switch ATM bit streams and very simple and compact.